import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-12-19
 * Time:22:19
 */

/**
 * 526. 优美的排列
 * 假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
 *     perm[i] 能够被 i 整除
 *     i 能够被 perm[i] 整除
 * 给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
 * 示例 1：
 * 输入：n = 2
 * 输出：2
 * 解释：
 * 第 1 个优美的排列是 [1,2]：
 *     - perm[1] = 1 能被 i = 1 整除
 *     - perm[2] = 2 能被 i = 2 整除
 * 第 2 个优美的排列是 [2,1]:
 *     - perm[1] = 2 能被 i = 1 整除
 *     - i = 2 能被 perm[2] = 1 整除
 */
public class countArrangement {
    boolean[] check;
    int ret;
    public int countArrangement(int n) {
        check = new boolean[n + 1];
        dfs(1,n);
        return ret;
    }

    private void dfs(int pos, int n) {
        if (pos == n + 1){
            ret++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (check[i] == false && (i % pos == 0 || pos % i == 0)){
                check[i] = true;
                dfs(pos + 1,n);
                check[i] = false;
            }
        }
    }
}
